188 HlSTOKY OF THE THEOKY OF NUMBEKS. [€HAP. VII
E. Prouhet32 gave, without reference, Crelle's18 method of forming the residues of the powers of a number. The object of the paper is to give a uniform method of proof of theorems, given in various places in Legendre's text, relating to the residues of the first n powers of an integer belonging to the exponent n modulo P, especially when P is a prime or a power of a prime, and the existence of primitive roots. He gave (p. 658) the usual proof that =*=2 is a primitive root of a prune 2#-j-l if q is a prime 4&=*= 1 (with a misprint).
C. F. Arndt33 proved that if g is a primitive root of the odd prime p and if px (X<n) is the highest power of p dividing G = g*~l — lJ then g belongs to the exponent pn~*(p — 1) modulo pn. Conversely, if the last is true of a primitive root g of p, then G is divisible by px and not by px+1. The first result with X = 1 shows that any primitive root of p2 is a primitive root of pn, n>2. Let g be a primitive root of p; if G is not divisible by p2, g is a primitive root of p2; but if G is divisible by p2, and h is not divisible by p} then g+hp is a primitive root of p2. Any odd primitive root of pn is a primitive root of 2pn. If g is a primitive root of pn or 2pn, and £ is a divisor of pn~1(p — 1), then if a ranges over the integers <t and prime to t, the </>(£) integers belonging to the exponent t modulo pn or 2pn are ge, where e = pn~1(p-l)a/L The numbers belonging to the exponent 2n~m modulo 2n are found more simply than by Gauss7 and Jacobi23 (p. 37).
P. L. Tchebychef34 proved that if a, j3,... are the distinct prime factors of p — 1, where p is a prime, then a is a primitive root of p if and only if no one of the congruences xa=a, o^=a,... (mod p) has an integral root. This furnishes a method (usually impracticable) of finding all primitive roots of p. A second method uses a number a belonging to the exponent n, and a number 6 not congruent to a power of a, and deduces a number belonging to an exponent >n. In the second supplement, he proved that 3 is a primitive root of any prime 22rl+l; that =±=2 is a primitive root of any prime 2a+l such that a is a prime 4&=±= 1; 3 is a primitive root of 4N2m+I if ra>0 and AT is a prime >92tn/(4-2m); 2 is a primitive root of any prime 4JV+1 such that N is an odd prime. The last result was later proposed35 as a question for solution (with reference to this text). There is given the table of primitive roots and indices for primes < 200, due to Ostrogradsky22. Schapira (p. 314) noted that in the list of errata in Jacobi's23 Canon (p. 222) there is omitted the error 8 for 6 in ind 14 for p = 25.
V. A. Lebesgue36 remarked that Cauchy's14 congruence Z=0 shows the existence of 0(n) integers belonging to the exponent n modulo p} a prime.
MNouv. Ann. Math., 5,1846,175-87, 659-62, 675-83.
»Jour. fur Math., 31,1846, 259-68.
"Theory of Congruences (in Russian), 1849. German translation by Schapira, Berlin, 1889,
p. 192. Italian translation by Mile. Massarini, Rome, 1895, with an extension of the
tables of indices to 353. »Nouv. Ann. Math., 15, 1856, 353. Solved by use of Euler's criterion by P, H. Rochette,
ibid., 16, 1857, 159. Also proved by Desmarest," p. 278. »«Nouv. Ann. Math., 8, 1849, 352; 11, 1852, 420.